package com.leetcode.algs4.graph;

/**
 * @author Dennis Li
 * @date 2020/6/16 15:14
 */
public class Digraph {
    private final int V;
    private int E;
    // 边的有向性体现在结点添加时，不像之前无向图，两端结点可以互达。
    // 有向图的节点是不一定可互达的
    private Bag<Integer>[] adj;

    public Digraph(int V) {
        this.V = V;
        this.E = 0;
        adj = (Bag<Integer>[]) new Bag[V];
        for (int i = 0; i < V; i++) {
            adj[V] = new Bag<>();
        }
    }

    public int V() {
        return V;
    }

    public int E() {
        return E;
    }

    public void addEdge(int v, int w) {
        adj[v].add(w);
        E++;
    }

    public Iterable<Integer> adj(int v) {
        return adj[v];
    }

    public Digraph reverse() {
        Digraph R = new Digraph(V);
        for (int i = 0; i < V; i++) {
            for (int w : adj(i)) {
                // 通过相反的方式添加边
                R.addEdge(w, i);
            }
        }
        return R;
    }

}
